package seqlist.oj;

/**
 * 回文链表
 */
public class Num234 {
    public boolean isPalindrome(ListNode head) {
        // 需要创建一个新链表，新链表是原链表的reverse(倒置)
        ListNode newHead = reverse(head);
        // 同步遍历原链表和新链表，当发现值不同时，return false
        while (head != null) {
            if (head.val != newHead.val) {
                return false;
            }
            head = head.next;
            newHead = newHead.next;
        }
        return true;
    }

    // 在LC或者牛客上，当一个方法无法完全的解决问题时，将多个步骤拆分为多个方法
    // 此处无需判断空，这个方法是我们自己调用的，就能保证他非空
    public ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode node = new ListNode(head.val);
            node.next = newHead;
            newHead = node;
            head = head.next;
        }
        return newHead;
    }

}
